package com.hardy.leetcode;

import java.util.Stack;

/**
 * User: Ruijie Date: 2016/8/18
 */
public class ReorderList {

    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int x){
            this.val=x;
        }
    }
    public static void reorderList1(ListNode head){
        if(head!=null){
            Stack<ListNode> stack=new Stack<ListNode>();
            ListNode temp=head;
            while(temp!=null){
                stack.push(temp);
                temp=temp.next;
            }
            ListNode cur=head;
            ListNode pre=stack.peek();
            pre.next=null;
            while(cur!=null&&cur.next!=pre&&cur!=pre){
                ListNode p=cur.next;
                pre.next=cur.next;
                cur.next=pre;
                cur=p;
                stack.pop();
                pre=stack.peek();
                pre.next=null;
            }
        }
    }
    public static void reorderList(ListNode head){
        if(head!=null){
            ListNode cur=head;
            ListNode pre=cur.next;
            while(cur!=null){
                ListNode tail=pre;
                while(pre!=null&&pre.next!=null){
                    tail=pre;
                    pre=pre.next;
                }
                if(tail!=null&&tail.next!=null){
                    tail.next=null;
                }
                ListNode temp=cur.next;
                cur.next=pre;
                if(pre!=temp){
                    pre.next=temp;
                }
                cur=temp;
                if(temp!=null){
                    pre=temp.next;
                }
            }
        }

    }

    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        ListNode cur=head;
        for(int i=2;i<=1000;i++){
            cur.next=new ListNode(i);
            cur=cur.next;
        }
       /* ListNode head=new ListNode(1);
        head.next=new ListNode(2);
        head.next.next=new ListNode(3);
        head.next.next.next=new ListNode(4);
        head.next.next.next.next=new ListNode(5);
        head.next.next.next.next.next=new ListNode(6);*/
        reorderList1(head);
        while(head!=null){
            System.out.print(head.val+" ");
            head=head.next;
        }
    }

}
